/*
 * @lc app=leetcode.cn id=729 lang=cpp
 *
 * [729] 我的日程安排表 I
 */
#include "include.h"
// @lc code=start
class MyCalendar {
public:
    MyCalendar() {
        // 描述一系列区间
        // 需要 ：有序
        // 1 : order
        // 2 : insert

        // --0--||--1--||--0--||--1--||--0--
        // -----s1-----e1-----s2-----e2-----
        //     [1,  0,  1,  0 ]
        //     [s1, e1, s2, e2]

        // 需要在一个有序序列中找到一个num的插入左右值
        // find a before num and b after num
        
        // check s3 e3

        // （1）保持有序，二分查找
        // 直接用 TreeSet 的 set / map
        // 对 end 找 lower_bound

        // （2）开线段树
    }
    
    bool book(int start, int end) {
        // first
        if (bookMap_.empty()){
            bookMap_.emplace(start, 1);
            bookMap_.emplace(end, 0);
            return true;
        }

        // Iterator pointing to first element equal to or greater than key, or end(). 
        // This function returns the first element of a subsequence of elements that matches the given key. 
        // If unsuccessful it returns an iterator pointing to the first element that has a greater value than given key or end() if no such element exists.
        auto iter = bookMap_.lower_bound(end);

        // end <= min
        if (iter == bookMap_.begin()){
            // printf("0 - %d %d\n", iter->first, iter->second);
            
            // check end

            // (1)
            // end = s0
            if (end == iter->first){
                bookMap_.erase(iter);
                bookMap_.emplace(start, 1);
            }else{
            // (2)
            // end < s0
                bookMap_.emplace(start, 1);
                bookMap_.emplace(end, 0);
            }
            
            // debug();
            return true;
        }
        else {
            // found end <= e0 or s0
            if (iter != bookMap_.end()){
                // iter next is end
                // is [s0 ----1--- e0---0]
                //    [s0 < end <= e0    ]
                if (iter->second == 0){
                    // printf("1 - %d %d\n", iter->first, iter->second);
                    // printf("insert fail %d %d\n", start, end);
                    return false;
                } else{
                // iter next is start
                // is [e0 ----0--- s0---1]
                //    [e0 < end <= s0    ]
                // need check start now

                auto s0 = iter;
                auto e0 = --iter;
                
                // (1)
                // start < e0 => false
                if (start < e0->first){

                    // printf("2_1 - (%d %d) (%d %d)\n", e0->first, e0->second, s0->first, s0->second);
                    // printf("insert fail %d %d\n", start, end);
                    return false;
                }

                // (2)
                // start = e0 and end < s0
                // => remove (e0, 0), add (end, 0)
                if (start == e0->first and end < s0->first){
                    // printf("2_2 - (%d %d) (%d %d)\n", e0->first, e0->second, s0->first, s0->second);
                    // printf("insert ok %d %d\n", start, end);

                    bookMap_.erase(e0);
                    bookMap_.emplace(end, 0);
                    
                    // debug();
                    return true;
                }

                // (3)
                // start = e0 and end = s0
                // remove (e0, 0), remove (s0, 1)
                if (start == e0->first and end == s0->first){
                    // printf("2_3 - (%d %d) (%d %d)\n", e0->first, e0->second, s0->first, s0->second);
                    // printf("insert ok %d %d\n", start, end);

                    bookMap_.erase(e0);
                    bookMap_.erase(s0);
                    
                    // debug();
                    return true;
                }

                // (4)
                // e0 < start and end < s0
                // add (start, 1), add (end, 0)
                if (e0->first < start and end < s0->first){
                    // printf("2_4 - (%d %d) (%d %d)\n", e0->first, e0->second, s0->first, s0->second);
                    // printf("insert ok %d %d\n", start, end);

                    bookMap_.emplace(start, 1);
                    bookMap_.emplace(end, 0);
                    
                    // debug();
                    return true;
                }

                // (5)
                // e0 < start and end = s0
                // add (start, 1), remove (s0, 0)
                if (e0->first < start and end == s0->first){
                    // printf("2_5 - (%d %d) (%d %d)\n", e0->first, e0->second, s0->first, s0->second);
                    // printf("insert ok %d %d\n", start, end);
                    
                    bookMap_.emplace(start, 1);
                    bookMap_.erase(s0);

                    // debug();
                    return true;
                }

                }
            }
            // max < end
            else{
                // is [s0 ----1--- e0-----0]
                //    [            e0 < end]
                // need check start and e0

                // rbegin() => reverse_iterator, not iterator
                // auto e0 = bookMap_.rbegin();
                auto e0 = std::prev( bookMap_.end() );

                // (1)
                // e0 < start < end
                // => add (start, 1), add (end, 0)
                if (e0->first < start){
                    // printf("3_1 - %d %d\n", iter->first, iter->second);
                    
                    bookMap_.emplace(start, 1);
                    bookMap_.emplace(end, 0);
                    // debug();
                    return true;
                }
                // (2)
                // e0 = start < end
                // => remove (e0, 0), add (end, 0)
                else if (e0->first == start){
                    // printf("3_2 - %d %d\n", iter->first, iter->second);

                    bookMap_.erase(e0);
                    bookMap_.emplace(end, 0);
                    // debug();
                    return true;
                }
                // (3)
                // start < e0 < end => false 
                else{
                    // printf("3_3 - %d %d\n", iter->first, iter->second);
                    // printf("insert fail %d %d\n", start, end);
                    return false;
                }
            }
        }

        return false;
    }
        // // Iterator pointing to the first element greater than key, or end().
        // auto iter2 = bookMap_.upper_bound(start);
private:
    // not <start, end>
    // but <vertex (start or end), flag (1 or 0)>
    std::map<int, int> bookMap_;

    // void debug(){
    //     for (auto& pair : bookMap_){
    //         printf("(%d %d) ", pair.first, pair.second);
    //     }
    //     printf("\n");
    // }

    // set<pair<int, int>> booked;
    // bool book2(int start, int end) {
    //     auto it = booked.lower_bound({end, 0});
    //     if (it == booked.begin() || (--it)->second <= start) {
    //         booked.emplace(start, end);
    //         return true;
    //     }
    //     return false;
    // }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */
// @lc code=end

// ["MyCalendar","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book"]\n[[],[20,29],[13,22],[44,50],[1,7],[2,10],[14,20],[19,25],[36,42],[45,50],[47,50],[39,45],[44,50],[16,25],[45,50],[45,50],[12,20],[21,29],[11,20],[12,17],[34,40],[10,18],[38,44],[23,32],[38,44],[15,20],[27,33],[34,42],[44,50],[35,40],[24,31]]

// ["MyCalendar","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book"]\n[[],[69,70],[3,4],[39,40],[35,36],[3,4],[55,56],[61,62],[97,98],[79,80],[76,77],[46,47],[78,79],[47,48],[38,39],[83,84],[90,91],[90,91],[49,50],[49,50],[77,78],[23,24],[89,90],[8,9],[3,4],[2,3],[48,49],[96,97],[4,5],[54,55],[30,31],[97,98],[65,66],[93,94],[49,50],[24,25],[17,18],[53,54],[45,46],[53,54],[32,33],[37,38],[5,6],[50,51],[48,49],[14,15],[91,92],[79,80],[73,74],[28,29],[31,32],[98,99],[37,38],[19,20],[49,50],[54,55],[37,38],[98,99],[12,13],[24,25],[46,47],[74,75],[87,88],[64,65],[61,62],[68,69],[28,29],[43,44],[89,90],[64,65],[72,73],[69,70],[88,89],[68,69],[28,29],[20,21],[64,65],[17,18],[40,41],[88,89],[22,23],[8,9],[33,34],[13,14],[19,20],[53,54],[99,100],[24,25],[82,83],[77,78],[90,91],[72,73],[33,34],[73,74],[0,1],[25,26],[69,70],[73,74],[12,13],[33,34],[47,48],[26,27],[77,78],[95,96],[28,29],[77,78],[28,29],[87,88],[16,17],[42,43],[51,52],[44,45],[63,64],[24,25],[18,19],[0,1],[45,46],[65,66],[21,22],[37,38],[77,78],[97,98],[24,25],[83,84],[20,21],[29,30],[66,67],[29,30],[37,38],[63,64],[15,16],[85,86],[61,62],[0,1],[23,24],[96,97],[91,92],[90,91],[80,81],[18,19],[69,70],[3,4],[59,60],[21,22],[75,76],[54,55],[65,66],[34,35],[19,20],[79,80],[6,7],[24,25],[29,30],[35,36],[9,10],[0,1],[73,74],[65,66],[78,79],[32,33],[58,59],[25,26],[3,4],[78,79],[92,93],[37,38],[91,92],[5,6],[79,80],[94,95],[78,79],[38,39],[16,17],[81,82],[34,35],[16,17],[33,34],[42,43],[34,35],[89,90],[88,89],[33,34],[68,69],[92,93],[73,74],[64,65],[91,92],[44,45],[13,14],[97,98],[64,65],[31,32],[91,92],[1,2],[57,58],[21,22],[38,39],[70,71],[84,85],[50,51],[58,59]]


class MySygmentTree {
struct MyNode {
    bool val = false, lazy = false;
    MyNode *left, *right;
    MyNode():val(false), lazy(false), left(nullptr), right(nullptr) {}
};
public:
    MySygmentTree(int l, int r):L(l), R(r){}
    bool query(int left, int right) {
        return _query(&root, L, R, left, right);
    }

    void update(int left, int right) {
        _update(&root, L, R, left, right);
    }

private:
    MyNode root;
    const int L, R;
    bool _query(MyNode *node, int l, int r, const int left, const int right) {
        if( left <= l && r <= right ) return node->val;
        pushDown(node);
        bool result = false;
        int m = l + r >> 1;
        if( left <= m ) result |= _query(node->left, l, m, left, right);
        if( right > m ) result |= _query(node->right, m+1, r, left, right);
        return result;
    }
    void _update(MyNode *node, int l, int r, const int left, const int right) {
        if( left <= l && r <= right ) {
            node->val = true;
            node->lazy = true;
            return;
        }
        pushDown(node);
        int m = l + r >> 1;
        if( left <= m ) _update(node->left, l, m, left, right);
        if( right > m ) _update(node->right, m+1, r, left, right);
        pushUp(node);
    }
    // 上推
    void pushUp(MyNode *node) {
        node->val = node->left->val || node->right->val;
    }
    // 下推
    void pushDown(MyNode *node) {
        if( !node->left ) node->left = new MyNode();
        if( !node->right ) node->right = new MyNode();
        if( !node->lazy ) return;
        node->left->val = true;
        node->right->val = true;
        node->left->lazy = true;
        node->right->lazy = true;
        node->lazy = false;
    }
};

class MyCalendar {
public:
    MyCalendar():mstree(0, 1e9) {

    }
    
    bool book(int start, int end) {
        if( mstree.query(start, end-1) ) return false;
        mstree.update(start, end-1);
        return true;
    }
private:
    MySygmentTree mstree;
};